package com.math;


import java.util.*;

/**
 * Definition for a binary tree node.
 *
 */

public class LevelTraversal {
    public static void main(String[] args) {
        TreeNode root = new TreeNode(1);
        TreeNode node1 = new TreeNode(2);
        TreeNode node2 = new TreeNode(3);
        TreeNode node3 = new TreeNode(4);
        TreeNode node4 = new TreeNode(5);
        TreeNode node5 = new TreeNode(6);
        TreeNode node6 = new TreeNode(7);

        root.left = node1;
        root.right = node2;
        node1.left = node3;
        node1.right = node4;
        node2.left = node5;
        node2.right = node6;

        LevelTraversal levelTraversal = new LevelTraversal();
//        List<ArrayList<Integer>> result = levelTraversal.levelPrint(root);
        List<ArrayList<Integer>> result = levelTraversal.getOrder(root);
        for (ArrayList<Integer> arrayList : result) {
            System.out.println(arrayList);
        }
    }

    private List<ArrayList<Integer>> levelPrint(TreeNode root) {
        if (root == null) {
            return null;
        }
        List<ArrayList<Integer>> result = new ArrayList<>();
        Deque<TreeNode> deque = new ArrayDeque<>();

        deque.push(root);
        while (!deque.isEmpty()) {
            int size = deque.size();
            ArrayList<Integer> path = new ArrayList<>();
            for (int i = 0; i < size; i++) {
                TreeNode node = deque.pop();
                path.add(node.val);
                if (node.left != null) {
                    deque.add(node.left);
                }
                if (node.right != null) {
                    deque.add(node.right);
                }
            }
            result.add(path);
        }
        return result;
    }

    private List<ArrayList<Integer>> getOrder(TreeNode root) {
        List<ArrayList<Integer>> result = new ArrayList<>();
        LinkedList<TreeNode> linkedList = new LinkedList<>();
        if (root != null) {
            linkedList.add(root);
        }
        int size = linkedList.size();

        while (size > 0) {
            ArrayList<Integer> item = new ArrayList<>();
            for (int i = 0; i < size; i++) {

                TreeNode node = linkedList.remove();
                item.add(node.val);
                if (node.left != null) {
                    linkedList.add(node.left);
                }
                if (node.right != null) {
                    linkedList.add(node.right);
                }
            }
            size = linkedList.size();
            result.add(item);
        }
        return result;
    }
}
